# TODO: 备选数字有哪些？
numQueue = []
for i in range(1, 9 + 1):
	numQueue.append(i)
# 用来回溯的栈
resultStack = []
# TODO: check point的格子有哪些？
checkPoint = [3, 6, 7, 8, 9]

ROWS = 3
COLS = 3

SUM = 15

# TODO: 如何初始化棋盘？
def InitBoard():
	'''初始化棋盘'''
	return [[0 for i in range(0, ROWS)] for i in range(0, COLS)]

board = InitBoard()
# ~ print(board)

# TODO: 如何从索引转化为行列组合？
def GetRowColFromIndex(idx):
    '''
    将索引转化成行列（2个分开的数）
    
    e.g.
	dix = 4
	1    2    3
	#4#   5    6
	7    8    9
	return 1, 0
    '''
    return idx // ROWS, idx % ROWS

# TODO: 如何判断即将要放置的数字是否可以放在这个格子里？
def IsFillingValueValid(cur_index, val):
	'''
	判断val是否刻意放进cur_index里
	
	参数
	cur_index -- 当前考察的格子的索引
	val -- 当前打算放在格子里的数字
	'''
	# 横向检测
	if val in board[cur_index[0]]:
		return False
	# 纵向检测
	for i in board:
		if val == i[cur_index[1]]:
			return False
	# 从左上到右下
	if cur_index[0] == cur_index[1]:
		for i in range(ROWS):
			if val == board[i][i]:
				return False
	# 从右上到左下
	if cur_index[0] + cur_index[1] == 2:
		for i in range(ROWS):
			if val == board[i][2 - i]:
				return False
	# 确保无误后返回“正确”
	return True

# TODO：如何获取比传入数字大并且尽可能接近传入的数字，而且还没有使用过的数字？
# 如果找到合适的数字则返回它，否则就返回-1
def GetBiggerUnusedNum(numm):
	num = numm
	while num < 9:
		num += 1
		check_continue = True
		for i in board:
			if check_continue == False:
				break
			for j in i:
				if num == j:
					check_continue = False
					break
		if num in numQueue:
			return num
	return -1

# TODO: 遇到check point格子的时候，计算这个格子应该放什么数字
# 如果计算得到的数字在备选容器里,则返回它，否则返回-1
def CalcCheckPointNum(curIndex):
	# 横向检测
	if val in board[cur_index[0]]:
		return False
	# 纵向检测
	for i in board:
		if val == i[cur_index[1]]:
			return False
	# 从左上到右下
	if cur_index[0] == cur_index[1]:
		for i in range(ROWS):
			if val == board[i][i]:
				return False
	# 从右上到左下
	if cur_index[0] + cur_index[1] == 2:
		for i in range(ROWS):
			if val == board[i][2 - i]:
				return False
	return -1

# TODO: 向指定格子放置一个数字
# 放置一个数字的时候不是简单的修改board上对应行列的值，而有三件事要处理，想想看是那三件事
def PutNum(curIndex, num):
    global numQueue,resultStack
    global board
    resultStack.append(numQueue.pop())
    board[curIndex[0]][curIndex[1]]
    return 0

def main():
    global board, numQueue
    # 当前要填的格子
    curIndex = 0

    while len(numQueue) > 0:
        # 如果index in checkPoint，则自动补最后一个数字
        r, c = GetRowColFromIndex(curIndex)
        # 是否需要回溯的标志
        needRollBack = False

        if board[r][c] == 0:
            # TODO：如果考察的格子为空格，应该进行哪些处理？
            num = min(numQueue)

            if needRollBack == True:
                # TODO：如果需要回溯的时候，需要做那些处理？              
				
			else:
				# TODO：不需要回溯的时候，需要做那些处理？
				PutNum([r, c], numQueue[-1])

    # TODO：输出找到的九宫格组合：
    print(board)

if __name__ == '__main__':
	main()
